package Offer;

import java.util.ArrayList;
import java.util.List;

//面试题08.07 无重复字符串的排列组合
//dfs
public class Offer08_07 {
    public String[] permutation(String S) {
        List<String> list = new ArrayList<>();
        boolean[] used = new boolean[S.length()];
        StringBuffer str = new StringBuffer();
        dfs(S,list,used,str);
        String[] res = new String[list.size()];
        list.toArray(res);
        return res;
    }
    public void dfs(String S,List<String> list,boolean[] used,StringBuffer str){
        if(str.length()==S.length()){
            String s= new String(str);
            list.add(s);
            return;
        }
        for(int i = 0 ; i < S.length();i++){
            if(used[i]==false) {
                str.append(S.charAt(i));
                used[i]=true;
                dfs(S,list,used,str);
                used[i]=false;
                str.deleteCharAt(str.length()-1);
            }
        }
    }
}
